1. Field of the Invention
The present invention relates to the field of electronic design automation (EDA). More specifically, the present invention relates to layout placement of cells within the field of electronic design automation used in the design and fabrication of integrated circuit devices.
2. Related Art
The rapid growth of the complexity of modern electronic circuits has forced electronic circuit designers to rely upon computer programs to assist and automate most steps of the integrated circuit design process. Typical circuits today contain hundreds of thousands or millions of individual pieces or xe2x80x9ccells.xe2x80x9d In many design architectures, the cells can have variable widths but constant heights or the cells can have variable heights but constant widths. Modern integrated circuit designs are much too large for a circuit designer or even an engineering team of designers to manage effectively by manual techniques. To automate the circuit design and fabrication of integrated circuit devices, electronic design automation (EDA) systems have been developed.
Within the automatic design process, an integrated circuit description is translated, by circuit synthesis processes, from a high level design language (HDL) format into a netlist description. The netlist description (xe2x80x9cnetlistxe2x80x9d) contains technology specific cells that are connected together by wire connections. The cells of the netlist are then placed by computer implemented placement processes that include a coarse placer process (also called a xe2x80x9cglobalxe2x80x9d placer). The coarse placer process assigns each cell with a substrate location defined by two dimensional coordinates (x, y). The coarse placer process places the cells in an effort to maintain certain circuit constraints such as: wire length minimization; signal delay minimizations; power constraints and substrate area constraints. The coarse placer process attempts to improve the quality of the integrated circuit design by minimizing the wire lengths between connected cells. The coarse placer process also avoids cell overlap with large obstacles.
However, the cell locations assigned by the coarse placer process are not initially legal locations for the cells because the coarse placer process assigns precise cell coordinates using floating point values. In the actual physical device, cells need to be assigned to locations that align within a matrix of allowable x and y discrete grid lines. Also, the cell locations determined by the coarse placer process may not be legal due to cell-to-cell overlaps or overlaps between cells and small obstacles. As a result of the above, a detailed (also called xe2x80x9cfinexe2x80x9d) placement process is used on the results of the coarse placer. The detailed placement process yields a legal cell placement that satisfies the following: (1) it aligns all cells to the x and y grid lines; (2) it contains no cell-to-cell overlaps; and (3) it contains no cell-to-obstacle overlaps. The detailed placement process generally does not attempt to improve wire length of the design, rather, it slightly degrades wire length in an effort to arrive at legal cell placements.
FIG. 1A illustrates a portion 10 of an exemplary cell layout as generated by a coarse placement process. Layout portion 10 contains cells 20a-20g having their upper left corners located at floating point coordinate positions that do not necessarily align with the horizontal 12 and vertical 14 lines of the (x, y) grid matrix. Therefore, these initial cell placements are not legal. For instance, assume cell 20a is located at (12.34, 43.92); cell 20b is located at (12.24, 47.52); cell 20c is located at (30.19, 47.56); cell 20d is located at (52.34, 16.12); cell 20e is located at (28.56, 59.11); cell 20f is located at (13.89, 69.21); and cell 20g is located at (39.01, 68.32). These placements from the coarse placer process are then provided to a detailed placer of the prior art which attempts to align the cells with the discrete (x, y) grid lines.
One prior art detailed placer process xe2x80x9csnapsxe2x80x9d all of the cells to their nearest grid intersection in an attempt to align the cell locations with the grid matrix. FIG. 1B illustrates such an output where the cells 20a-20g are xe2x80x9csnappedxe2x80x9d to the nearest grid intersection. For instance, cell 20c is snapped to location (30, 45), cell 20d is snapped to location (15, 50), cell 20e is snapped to location (25, 55), cell 20f is snapped to location (15, 65) and so forth. However, cells 20b and 20a share the same grid location (10, 40) and therefore overlap with each other. This detailed placement process of the prior art has a disadvantage in that many cells, after being snapped to their nearest grid locations, end up overlapping other cells, sometimes causing thousands of overlaps. The problem is severe because when the detailed placer process attempts to move an overlapping cell to another location, it must also check for a possible overlap condition at the new location, and so forth. This process of moving cells, checking for overlapping conditions and moving cells, etc., can take many iterations per cell thereby consuming a relatively large amount of processing time. In an effort to reduce this problem, complex, detailed and time consuming programming processes are introduced which add processing penalties and technical complexities to the detailed placer process.
In addition to taking a relatively large amount of processing time to complete, this prior art method of detailed placement also causes some cells to be moved quite a distance from their original position in order to locate a non-overlapping site. This is especially true for high density cell layouts. Another disadvantage of this prior art detailed process is that it does not fully take advantage of the two dimensional nature of the detailed placement problem and thereby generates cell placements that are not typically uniform in nature. Another disadvantage of this detailed cell placement process is that it does not easily or readily deal with cell obstructions. In order to cope with cell obstructions in the layout area, complex and detailed heuristics need to be incorporated into the prior art detailed placement process.
Accordingly, what is needed is a detailed placer process that yields grid aligned legal coordinates but does not consume a relatively long processing period to compute. What is also needed is a detailed placer process that does not move the cells very far from their original positions as determined from the coarse placer process. What is needed further is a detailed placer process that yields a relatively uniform placement while avoiding cell-to-cell overlaps and avoiding cell-to-obstruction overlaps. The present invention provides these advantages. These and other advantages of the present invention not specifically mentioned above will become clear within discussions of the present invention presented herein.
A method and system are described herein for high speed detailed placement of cells within an integrated circuit design. The novel detailed placement system receives a set of cells of an integrated circuit design where the cells have undergone coarse placement. Cells have variable width but the same height (or vice-versa in other embodiments). As a result of coarse placement, the cells are each assigned an initial coordinate position, e.g., using floating point precision values. During detailed placement, the cell coordinates are assigned to non-overlapping positions within x-axis and y-axis grid lines.
The detailed placement process of the present invention sorts the cells based on their coordinate values along a first axis, e.g., their x-axis coordinates. This sort order dictates the cell placement order during the detailed placement process. In one embodiment, sort order preference is given to the wider cells to place them earlier in the placement process. Preference can be given, in one implementation, by subtracting a weighted product of the cell""s width from the cell""s initial coordinate position. For a given cell, placement is performed by scanning through the rows of the substrate and selecting the left-most positioned vacant cell site of each row as a candidate site for placement of the given cell. A group of candidate sites is determined because each row yields a candidate. A cell site is a grid based placement position. A site is vacant if it does not contain a previously placed cell. Of the candidate sites, a valid site having the lowest cost (e.g., the nearest site) is selected for the given cell. Some candidate sites are invalid due to the presence of obstructions or incompatible metal layers in the integrated circuit design. A candidate site can also be invalid if it lies too far to the left of the cell, based on a determined left factor. Placement from left to right along the rows continues in the above manner until all cells are detail placed. Alternatively, the placement process of the present invention could run right to left, down to up or up to down. The present invention operates particularly well for integrated circuit designs having 97 percent utilization or less.
Embodiments of the present invention include a computer controlled detailed placement method having the steps of: a) accessing a netlist description of an integrated circuit having cells of a common height wherein each cell has assigned thereto an initial two dimensional coordinate position within an area; b) sorting the cells into a sort order based on a coordinate value of each cell; c) assigning a plurality of rows to the area; d) based on the sort order, selecting an unaligned cell and traversing the plurality of rows to determine candidate sites for placement of the unaligned cell wherein the candidate sites are the left-most vacant sites of each row and wherein each candidate site is aligned within a two dimensional grid matrix; e) placing the unaligned cell in a lowest cost candidate site of the candidate sites of step d); and f) aligning all of the cells to the grid matrix by repeating steps d)-e) for each cell of the netlist description.
Embodiments include the above and where step e) comprises the steps of: e1) determining the lowest cost site by selecting a candidate site that is closest to the initial coordinate position of the unaligned cell; and e2) placing the unaligned cell in the lowest cost candidate site as determined at the step e1). Embodiments include the above and wherein the coordinate value of step b) is within a horizontal coordinate axis and wherein the step b) comprises the steps of: b1) assigning a new coordinate position to each cell by shifting each cells"" horizontal coordinate position by an amount dependent on the width of each cell; and b2) weighting wider cells higher in the sort order by sorting the cells based on their new coordinate positions as determined at step b1). Embodiments also include a computer system implemented in accordance with the above.